#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define RANDOM_RANGE 1000

void generateRandom(int **arr, int size)
{
    if (*arr == NULL)
        *arr = (int *)malloc(sizeof(int) * size);
    int *ptr = *arr;
    for (int i = 0; i < size; i++)
    {
        ptr[i] = rand() % RANDOM_RANGE;
    }
}

void displayArr(int *arr, int size)
{
    if (arr != NULL)
    {
        for (int i = 0; i < size; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
}

//////////////////////// TODO: HeapSort

void Insert(int *A, int size, int x)
{
    int hole = size++;
    while (hole > 0 && x > A[(hole - 1) / 2])
    {
        A[hole] = A[(hole - 1) / 2];
        hole = (hole - 1) / 2;
    } // insert value is bigger than its parent,swap hole position and the parent
    A[hole] = x; // insert
    return;
}
int DeleteMax(int *A, int size)
{
    int max = A[0];
    int hole = 0;
    int x = A[--size];                // store last element
    while ((hole + 1) * 2 - 1 < size) // A[hole] has children
    {
        int bid;
        int child1 = (hole + 1) * 2 - 1;
        if (child1 + 1 == size) // only one child
        {
            bid = child1;
        }
        else
        {
            bid = A[child1] > A[child1 + 1] ? child1 : child1 + 1; // select the index of bigger child
        }
        if (x >= A[bid]) // insert value is bigger than child, exit loop
            break;
        // swap hole with the bigger child
        A[hole] = A[bid];
        hole = bid;
    }
    A[hole] = x; // insert
    return max;
}
void HeapSort(int *A, int n)
{
    for (int i = 0; i < n; i++)
    {
        Insert(A, i, A[i]);
    }
    for (int j = n - 1; j >= 0; j--)
    {
        A[j] = DeleteMax(A, j + 1);
    }
}

/***************************
 * Implement HeapSort
 * *************************/

int main(int argc, char const *argv[])
{
    // Don't change this
    // srand(time(NULL));
    srand(1);

    unsigned long t;
    double cpu_time_used;

    int size = 20;
    int *A1 = NULL;
    generateRandom(&A1, size);
    printf("Value of A1 before HeapSort:\n");
    displayArr(A1, size);

    // TODO:
    HeapSort(A1, size);
    printf("Value of A1 after HeapSort:\n");
    displayArr(A1, size);

    free(A1);
    A1 = NULL;

    size = 10000;
    generateRandom(&A1, size);
    printf("Value of A1 before HeapSort:\n");
    displayArr(A1, 20);

    t = clock();
    // TODO:
    HeapSort(A1, size);
    t = clock() - t;
    double time_taken = ((double)t) / CLOCKS_PER_SEC; // in seconds
    printf("Value of A1 after HeapSort:[%f]\n", time_taken);

    displayArr(A1, 20);

    return 0;
}

/*************************************** sample output
Value of A1 before HeapSort:
807 249 73 658 930 272 544 878 923 709 440 165 492 42 987 503 327 729 840 612
Value of A1 after HeapSort:
42 73 165 249 272 327 440 492 503 544 612 658 709 729 807 840 878 923 930 987
Value of A1 before HeapSort:
303 169 709 157 560 933 99 278 816 335 97 826 512 267 810 633 979 149 579 821
Value of A1 after HeapSort: [0.000030]
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
***************************************/